/*
 * @lc app=leetcode.cn id=322 lang=cpp
 *
 * [322] 零钱兑换
 */
#include <algorithm>
#include <vector>
using std::vector;

// @lc code=start
class Solution
{
  public:
    int coinChange(vector<int> &coins, int amount)
    {
        if (amount == 0) {
            return 0;
        }
        int MAX_CHANGE = amount + 1;
        // dp[i][j] 表示前i个硬币凑出零钱j所需要的最少硬币数量
        vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, MAX_CHANGE));

        // 零钱0，需要的最少硬币数量为0
        for (int i = 0; i < coins.size(); ++i) {
            dp[i][0] = 0;
        }

        for (int i = 1; i <= coins.size(); ++i) {
            for (int j = 1; j <= amount; ++j) {
                if (coins[i - 1] > j) {
                    // 硬币面值太大，不选择硬币
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选择硬币和不选择硬币，二者取最小值
                    dp[i][j] = std::min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                }
            }
        }

        return dp[coins.size()][amount] == MAX_CHANGE ? -1 : dp[coins.size()][amount];
    }
};
// @lc code=end
